| 翻訳と辞書 |
| König's lemma ： ウィキペディア英語版 |
König's lemma
König's lemma or König's infinity lemma is a theorem in graph theory due to .〔Note that, although Kőnig's name is properly spelled with a double acute accent, the lemma named after him is customarily spelled with an umlaut.〕〔 as explained in 〕 It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in mathematical logic, especially in computability theory. This theorem also has important roles in constructive mathematics and proof theory.
==Statement of the lemma==
If ''G'' is a connected graph with infinitely many vertices such that every vertex has finite degree (that is, each vertex is adjacent to only finitely many other vertices) then ''G'' contains an infinitely long simple path, that is, a path with no repeated vertices.
A common special case of this is that every tree that contains infinitely many vertices, each having finite degree, has at least one infinite simple path.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「König's lemma」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|